﻿using System;
using System.Collections.Generic;
using PPClasses;

namespace PortalPlan.Solvers
{
    internal class SA : Solver
    {
        List<Portal> Portals;
        List<PortalPair> Links;

        double CrossCost;
        double LinkCost;

        Random r;

        public SA(List<Portal> points) :
             base(points)
        {
        }

        public override String StatusText()
        {
            return "SA: " + BestScore.Links + " links, " + BestScore.Tris + " fields = " + BestScore.Score +
                       " AP.  " + (Stop ? "Stopped.  " : "") +
                       (CompletelyDone ? "Done.  " : "");
        }

        public override void GoGoGo()
        {
            List<PortalPair> pp = new List<PortalPair>();
            foreach (Pair p in PairChoices)
            {
                pp.Add(new PortalPair { PortalA = PortalPoints[p.a], PortalB = PortalPoints[p.b] });
            }

            int n = PairChoices.Count;

            SA_Alg(PortalPoints, pp);
            CompletelyDone = true;
        }

        public override bool CanThread
        {
            get { return false; }
        }

        public List<PortalPair> SA_Alg(List<Portal> portals, List<PortalPair> links)
        {
            return this.SA_Alg(portals, links, 5, -1.0);
        }

        public List<PortalPair> SA_Alg(List<Portal> portals, List<PortalPair> links, double crossCost, double linkCost)
        {
            this.Portals = portals;
            this.Links = links;

            CrossCost = crossCost;
            LinkCost = linkCost;

            r = new Random(DateTime.Now.Millisecond);

            if (links == null || links.Count == 0)
                links = initialise();

            double lastCost = cost(links);
            double bestCost = lastCost;
            List<PortalPair> bestLinks = links;

            double T = Math.Max(1000, portals.Count * Math.Abs(lastCost));

            long maxI = Math.Max(1000, (long)Math.Pow(portals.Count, 3));
            for (long l = 0; l < maxI; l++)
            {
                List<PortalPair> candidateLinks = neighbour(links);
                double candidateCost = cost(candidateLinks);

                if (candidateCost < lastCost || r.NextDouble() < Math.Exp((lastCost - candidateCost) / T))
                {
                    links = candidateLinks;
                    lastCost = candidateCost;

                    if (candidateCost < bestCost)
                    {
                        bestCost = candidateCost;
                        bestLinks = candidateLinks;

                        List<Pair> pp = new List<Pair>();
                        foreach (var p in candidateLinks)
                        {
                            int n1 = PortalPoints.IndexOf(p.PortalA);
                            int n2 = PortalPoints.IndexOf(p.PortalB);
                            pp.Add(new Pair(n1, n2));
                        }
                        EvaluateSolution(pp, true);
                    }
                }

                T *= 0.9;
            }

            return bestLinks;
        }

        private List<PortalPair> initialise()
        {
            List<PortalPair> links = new List<PortalPair>();

            for (int i = 0; i < Portals.Count; i++)
                for (int j = i + 1; j < Portals.Count; j++)
                    if (r.NextDouble() < 0.05)
                        links.Add(new PortalPair() { PortalA = Portals[i], PortalB = Portals[j] });

            return links;
        }

        private List<PortalPair> neighbour(List<PortalPair> links)
        {
            List<PortalPair> newLinks = new List<PortalPair>(links);

            if (r.NextDouble() < 0.5) // Add link
            {
                while (true)
                {
                    PortalPair l = new PortalPair() { PortalA = Portals[r.Next(0, Portals.Count)], PortalB = Portals[r.Next(0, Portals.Count)] };

                    if (l.PortalA == l.PortalB)
                        continue;

                    bool exists = false;
                    foreach (PortalPair lnk in links)
                    {
                        if ((lnk.PortalA == l.PortalA && lnk.PortalB == l.PortalB) ||
                            (lnk.PortalB == l.PortalA && lnk.PortalA == l.PortalB))
                        {
                            exists = true;
                            break;
                        }
                    }

                    if (exists)
                        continue;

                    newLinks.Add(l);
                    break;
                }
            }
            else if (links.Count > 0) // delete link
            {
                List<PortalPair> crossingLinks = new List<PortalPair>();
                
                for (int i = 0; i < links.Count; i++)
                    for (int j = i + 1; j < links.Count; j++)
                        if (linkPrecludes(links[i], links[j]))
                        {
                            crossingLinks.Add(links[i]);
                            crossingLinks.Add(links[j]);
                        }
                
                if (crossingLinks.Count > 0)
                    newLinks.RemoveAt(newLinks.IndexOf(crossingLinks[r.Next(0, crossingLinks.Count)]));
                else
                    newLinks.RemoveAt(r.Next(0, newLinks.Count));
            }

            return newLinks;
        }

        private double cost(List<PortalPair> links)
        {
            double cost = LinkCost * links.Count;

            for (int i = 0; i < links.Count; i++)
                for (int j = i + 1; j < links.Count; j++)
                    if (linkPrecludes(links[i], links[j]))
                        cost += CrossCost;

            return cost;
        }

     
        private bool linkPrecludes(PortalPair linkA, PortalPair linkB)
        {
            Portal A = linkA.PortalA;
            Portal B = linkA.PortalB;
            Portal C = linkB.PortalA;
            Portal D = linkB.PortalB;

            if (A == C || A == D || B == C || B == D)
                return false;

            if ((A.X < C.X && A.X < D.X && B.X < C.X && B.X < D.X) ||
                (A.X > C.X && A.X > D.X && B.X > C.X && B.X > D.X) ||
                (A.Y < C.Y && A.Y < D.Y && B.Y < C.Y && B.Y < D.Y) ||
                (A.Y > C.Y && A.Y > D.Y && B.Y > C.Y && B.Y > D.Y))
                return false;

            double denom = (A.X - B.X) * (C.Y - D.Y) - (A.Y - B.Y) * (C.X - D.X);
            if (Math.Abs(denom) < 0.000000001)
                return false;

            double u = A.X * B.Y - A.Y * B.X;
            double v = C.X * D.Y - C.Y * D.X;

            double x_intersect = (u * (C.X - D.X) - v * (A.X - B.X)) / denom;
            double y_intersect = (u * (C.Y - D.Y) - v * (A.Y - B.Y)) / denom;

            if (x_intersect > Math.Min(A.X, B.X) && x_intersect < Math.Max(A.X, B.X) &&
                x_intersect > Math.Min(C.X, D.X) && x_intersect < Math.Max(C.X, D.X) &&
                y_intersect > Math.Min(A.Y, B.Y) && y_intersect < Math.Max(A.Y, B.Y) &&
                y_intersect > Math.Min(C.Y, D.Y) && y_intersect < Math.Max(C.Y, D.Y))
                return true;

            return false;
        }
    }
}

